# LeetCode 264、丑数II（动态规划）
# 一、题目描述
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1是丑数。n不超过1690。
# 二、题目解析
对于任意一个丑数来说，它都可以和 2、3、5 进行相乘得到一个丑， 那么每个丑数都可以得到三个数，这三个数分别属于不同的数组中。
假设当前已经知道丑数序列 nums 是这些元素：1, 2, 3, 4, 5, 6, 8, 9 。
1、nums2 数组存储了这个序列中所有丑数与 2 相乘的结果，nums2 = { 1 * 2 ， 2 * 2 ，3 * 2 ， 4 * 2 ，5 * 2 ，6 * 2 ，8 * 2，。。。}
2、nums3 数组存储了这个序列中所有丑数与 3 相乘的结果，nums3 = { 1 * 3 ， 2 * 3 ，3 * 3 ， 4 * 3 ，5 * 3 ，6 * 3 ，8 * 3，。。。}
3、nums5 数组存储了这个序列中所有丑数与 5 相乘的结果，nums5 = { 1 * 5 ， 2 * 5 ，3 * 5 ， 4 * 5 ，5 * 5 ，6 * 5 ，8 * 5，。。。}
那么，想填充 nums 的话，它的选择来源肯定只能来源于 nums2 、nums3、nums5 这三个数组。
并且 nums 序列接下来填充的数是 nums2 、nums3、nums5 这三个数组除去已经在 nums 序列的丑数时剩下的最小值。
也就是说，每次寻找丑数的过程是在 nums2 、nums3、nums5 这三个数组中寻找最小值的过程。
- 1、在寻找过程中，因为丑数的序列在不断的扩充，nums2 、nums3、nums5 这三个数组也在不断的扩充。
- 2、每次找到那个最小值之后，接下来的寻找过程应该忽略它了。
那么，现在来看 nums2 、nums3、nums5 这三个数组的起始状态，此时，丑数序列只有一个元素 ugly[0] = 1 。
- nums2 ：{1 * 2......}
- nums3： {1 * 3......}
- nums5 ：{1 * 5......}
第二个丑数序列需要去获取 nums2 、nums3、nums5 这三个数组的第一个元素的最小值。
那么，此时可以设置三个索引，分别指向 nums2、nums3、nums5 数组开始的位置。
- index2 指向 nums2 数组
- index3 指向 nums3 数组
- index5 指向 nums5 数组
比较的结果是发现 1 * 2 最小，于是第二个丑数找到了，此时 ugly 就变成 { 1 , 2 } ，nums2 、nums3、nums5 这三个数组也需要得到扩充。
- nums2 ：{1 * 2 ，2 * 2 ，......}
- nums3： {1 * 3， 2 * 3 ，......}
- nums5 ：{1 * 5， 2 * 5 ，......}
刚才我们说过，每次找到那个最小值之后，接下来的寻找过程应该忽略它了，用代码的形式来表示就是索引值向后移动。
比如在 nums2 上找到了 1 * 2 之后，index2 开始移动到 2 * 2 的位置。
第三个丑数序列需要去获取 nums2 、nums3、nums5 这三个数组中 index2、index3、index5 指向元素的最小值。
- index2 指向了 nums2 中的 2 * 2，即 nums2[index2]
- index3 指向了 nums3 中的 1 * 3，即 nums3[index3]
- index5 指向了 nums5 中的 1 * 5，即 nums5[index5]
如此不断的循环，就可以把 ugly 数组填充到 n 的位置，得到 ugly[n]。
这里需要注意到， nums2 、nums3、nums5 这三个数组并没有具体的额外创造出来，它们都在 ugly 数组中。
- nums2 实际上就是 ugly[]*2 的结果
- nums3 实际上就是 ugly[]*3 的结果
- nums5 实际上就是 ugly[]*5 的结果
所以比较的过程，实际上就是比较 nums2[index2] = ugly[index2] * 2 、 nums3[index3] = ugly[index3] * 3、 nums5[index5] = ugly[index5] * 5 三者大小的过程，获取到最小值就填充到 ugly 数组中，再将对应的索引向后移动，由于 nums2 、nums3、nums5 这三个数组中会存在重复元素，所以需要执行去重的操作。
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
public int nthUglyNumber(int n) {
// 设置一个数组，用来存放结果
// nums[0] 表示第 1 个丑数，结果是 1
// nums[1] 表示第 2 个丑数，结果是 2
// nums[n-1] 表示第 n 个丑数，结果需要计算
int[] nums = new int[n];
// nums[0] 表示第 1 个丑数，结果是 1
nums[0] = 1;
// 对于任意一个丑数来说，它总是可以由前面的丑数与 2、3、5 其中一个进行相乘而来的
// 那么每个丑数都可以得到三个数，这三个数分别属于不同的数组中
// nums2 = {1*2, 2*2, 3*2, 4*2, 5*2, 6*2, 8*2...}
// nums3 = {1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 8*3...}
// nums5 = {1*5, 2*5, 3*5, 4*5, 5*5, 6*5, 8*5...}
// nums2 按照从小到大的顺序存放了所有丑数和 2 相乘的结果
// nums3 按照从小到大的顺序存放了所有丑数和 3 相乘的结果
// nums5 按照从小到大的顺序存放了所有丑数和 5 相乘的结果
// nums[i] 的值就是在这三个数组中进行挑选
// 设置三个索引，分别指向 nums2、nums3、nums5 数组开始的位置
// 每当 nums[i] 的值从哪个数组中获取到，该索引就在这个数组中向后移动
// index2 指向 nums2 数组
int index2 = 0;
// index3 指向 nums3 数组
int index3 = 0;
// index5 指向 nums5 数组
int index5 = 0;
// 开始填充 nums 数组
for (int i = 1; i < n; i++) {
// nums[i] 的值就是在这三个数组中进行挑选最小值
// 但是，这三个数组并没有具体的额外创造出来，它们都在 nums 数组中
// 其中 nums[index2] 表示的就是第 index2 个丑数，nums[index2] * 2 在数组 nums2 中的位置为 index2
// 其中 nums[index3] 表示的就是第 index3 个丑数，nums[index3] * 3 在数组 nums3 中的位置为 index3
// 其中 nums[index5] 表示的就是第 index5 个丑数，nums[index5] * 5 在数组 nums5 中的位置为 index5
nums[i] = Math.min(Math.min(nums[index2] * 2, nums[index3] * 3), nums[index5] * 5);
// 执行完上面的代码之后，nums[i] 已经被填充完毕
// 那么和它相等的数需要被挪出接下来的比较
// nums[i] == nums[index2] * 2
// 移动 index2 到下一个数
if (nums[i] == nums[index2] * 2) {
index2++;
}
// nums[i] == nums[index3] * 3
// 移动 index3 到下一个数
if (nums[i] == nums[index3] * 3) {
index3++;
}
// nums[i] == nums[index5] * 5
// 移动 index5 到下一个数
if (nums[i] == nums[index5] * 5) {
index5++;
}
}
// 返回结果
return nums[n - 1];
}
}
# 四、复杂度分析
- 时间复杂度 O(N) ： 其中 N = n ，有个 for 循环，需遍历列表。
- 空间复杂度 O(N) ： 创造了长度为 N 的结果数组，需要使用 O(N)的额外空间。